package day190707;

import java.util.ArrayList;
import java.util.List;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/7 上午 10:17
 * 46. 全排列
 * https://leetcode-cn.com/problems/permutations/
 */
public class Permute {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        doPermute(nums, nums.length, nums.length, result);
        return result;
    }

    private void doPermute(int[] nums, int length, int k, List<List<Integer>> result) {
        if (k == 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < length; i++) {
                list.add(nums[i]);
            }
            result.add(list);
        }

        for (int i = 0; i < k; i++) {
            int temp = nums[i];
            nums[i] = nums[k - 1];
            nums[k - 1] = temp;
            doPermute(nums, length, k - 1, result);
            temp = nums[i];
            nums[i] = nums[k - 1];
            nums[k - 1] = temp;
        }
    }


}
